// 二叉搜索树的删除节点
class Solution {
 public:
  TreeNode* deleteNode(TreeNode* root, int key) {
    if (root == nullptr)
      return root;  // 第一种情况：没找到删除的节点，遍历到空节点直接返回了
    if (root->val == key) {
      // 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
      // 第三种情况：其左孩子为空，右孩子不为空，删除节点，右孩子补位
      // ，返回右孩子为根节点
      if (root->left == nullptr) return root->right;
      // 第四种情况：其右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
      else if (root->right == nullptr)
        return root->left;
      // 第五种情况：左右孩子节点都不为空，则将删除节点的左子树放到删除节点的右子树的最左面节点的左孩子的位置
      // 并返回删除节点右孩子为新的根节点。
      else {
        TreeNode* cur = root->right;  // 找右子树最左面的节点
        while (cur->left != nullptr) {
          cur = cur->left;
        }
        cur->left =
            root->left;  // 把要删除的节点（root）左子树放在cur的左孩子的位置
        TreeNode* tmp = root;  // 把root节点保存一下，下面来删除
        root = root->right;    // 返回旧root的右孩子作为新root
        delete tmp;  // 释放节点内存（这里不写也可以，但C++最好手动释放一下吧）
        return root;
      }
      /*
       else {  // 左右子树都存在
                TreeNode* temp = root->left;
                while(temp->right) temp=temp->right;
                temp->right=root->right;
                TreeNode* del = root;
                root=root->left;
                delete del;
                return root;
            }
      */
    }
    if (root->val > key) root->left = deleteNode(root->left, key);
    if (root->val < key) root->right = deleteNode(root->right, key);
    return root;
  }
};

// 普通二叉树的删除节点
class Solution {
 public:
  TreeNode* deleteNode(TreeNode* root, int key) {
    if (root == nullptr) return root;
    if (root->val == key) {
      if (root->right == nullptr) {  // 这里第二次操作目标值：最终删除的作用
        return root->left;
      }
      TreeNode* cur = root->right;
      while (cur->left) {
        cur = cur->left;
      }
      swap(root->val,
           cur->val);  // 这里第一次操作目标值：交换目标值其右子树最左面节点。
    }
    root->left = deleteNode(root->left, key);
    root->right = deleteNode(root->right, key);
    return root;
  }
};